package com.lw.leetcode.other.b;

/**
 * Created with IntelliJ IDEA.
 * LCP 23. 魔术排列
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/18 14:17
 */
public class IsMagic {

    public static void main(String[] args) {
        IsMagic test = new IsMagic();

        // true
//        int[] arr = {2, 4, 3, 1, 5};

        // true
        int[] arr = {2, 4, 6, 1, 5, 9, 3, 8, 7};

        // false
//        int[] arr = {5, 4, 3, 2, 1};

        boolean magic = test.isMagic(arr);
        System.out.println(magic);
    }

    public boolean isMagic(int[] target) {
        if (target[0] != 2) {
            return false;
        }
        int length = target.length;
        int[] arr = new int[length];
        int[] item = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = i + 1;
        }
        find(arr, item, 0);
        int k = 0;
        for (; k < length; k++) {
            if (item[k] != target[k]) {
                break;
            }
        }
        int st = k;
        while (st < length) {
            System.arraycopy(item, st, arr, st, length - st);
            find(arr, item, st);
            int l = Math.min(length, st + k);
            for (int i = st; i < l; i++) {
                if (item[i] != target[i]) {
                    return false;
                }
            }
            st += k;
        }
        return true;
    }

    private void find(int[] arr, int[] item, int st) {
        int length = arr.length;
        if (st == length - 1) {
            return;
        }
        int i = st;
        int j = st + 1;
        while (i < length) {
            item[i] = arr[j];
            i++;
            j += 2;
            if (j >= length) {
                j = st;
            }
        }
    }
}
